package com.hubu.map;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
public class JavaHashMap<K,V> {
    private int size;
    private static final int DEFAULT_CAPACITY = 16;
    private static final float DEFAULT_LOAD_FACTOR = 0.75F;
    private static final int TREEIFY_THRESHOLD = 8;
    static final int MIN_TREEIFY_CAPACITY = 64;
    static final int UNTREEIFY_THRESHOLD = 6;
    private int capacity;
    private float loadFactor;
    private int threshold;
    private Entry<K, V>[] table = null;
    public JavaHashMap(int capacity, float loadFactor) {
        this.capacity = capacity;
        this.loadFactor = loadFactor;
        this.threshold = (int) (this.capacity * 0.75);
    }
    public JavaHashMap() {
        this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    interface  Entry<K,V>{
        K getKey();
        V getValue();
        void setKey(K key);
        void setValue(V value);
    }
    public void  put(K key,V value){
        V oldValue=null;
        int length=0;
        if(table==null||(length=table.length)==0){
            table=new Entry[this.capacity];
        }
        int hash=hash(key);
        int index=index(hash,table.length);
        if(table[index]==null){
            table[index]=new Node<>(hash,key,value,null);
        }
        Entry<K,V> entry=table[index];
        Entry<K,V> e=null;//记录返回结果
        if(entry instanceof TreeNode){
            TreeNode<K,V> treeNode= (TreeNode<K, V>) entry;
            TreeNode<K,V> newNode=new TreeNode<>(hash,key,value);
           e= putTreeNode(treeNode, newNode);
           return ;
        }
        Node<K,V> current= (Node<K, V>) entry;
        int binCount=0;
        for(binCount=0;;binCount++){
            if((current.hash==hash&&current.key.equals(key))||key==current.key){
                e=current;
                oldValue=current.value;
                current.key=key;
                current.value=value;
                break;
            }
            if(current.next==null){
                current.next=new Node<>(hash,key,value,null);
                //当链表的长度到第9个节点的时候，链表将会转换成为红黑树
                if(binCount>=TREEIFY_THRESHOLD-1){
                    tryChangeToRedBlackTree(hash);
                }
                break;
            }
            current=current.next;
        }
        if(e!=null){
            return ;
        }
        if(++size>threshold){
            resize();
        }
    }
    public V remove(K key){
        int hash=hash(key);
        int index=index(hash,table.length);
        Entry<K,V> entry=table[index];
        if(entry==null) return null;
        V value=null;
        if(entry instanceof Node){
            Node<K,V> cur= (Node<K, V>) entry;
            if(Objects.equals(cur.key,key)){
                value=cur.value;
                table[index]=cur.next;
            }
            else{
                while(cur.next!=null){
                    if(Objects.equals(key,cur.next.key)){
                        value=cur.value;
                        cur.next=cur.next.next;
                    }
                    cur=cur.next;
                }
            }
        }
        else{
            TreeNode<K,V> rootNode= (TreeNode<K, V>) entry;
            TreeNode<K,V> treeNode=node(rootNode,key);
            value=treeNode.value;
            removeTreeNode(treeNode,index,table);
        }
        return value;
    }
    /**
     *
     * @param treeNode 待删除的节点
     * @param index 索引
     * @param table 表
     * @return V
     */
    private V removeTreeNode(TreeNode<K, V> treeNode, int index, Entry<K, V>[] table) {
        TreeNode<K,V> current= (TreeNode<K, V>) table[index];
        if(treeNode.left!=null&&treeNode.right!=null){
            //寻找后继节点
            TreeNode<K,V> p=successor(treeNode);
            //p就是要删除的节点
            treeNode.hash=p.hash;
            treeNode.key=p.key;
            treeNode.value=p.value;
            treeNode.color=p.color;
            //让treeNode指向p
            treeNode=p;
        }
        //删除一个节点的情况
        TreeNode<K,V> replacement=treeNode.left!=null?treeNode.left:treeNode.right;
        if(replacement!=null){
            replacement.parent=treeNode.parent;
            if(treeNode.parent==null){
                table[index]=replacement;
            }
            else if(treeNode==treeNode.parent.left){
                treeNode.parent.left=replacement;
            }
            else if(treeNode==treeNode.parent.right){
                treeNode.parent.right=replacement;
            }
            treeNode.parent=treeNode.left=treeNode.right=null;
            //如果该节点是黑色 它的子节点必然是红色，直接染黑就可以
            if(treeNode.color==BLACK){
                afterRemove(replacement,index,table);
            }
        }
        else{
            if(treeNode.color==BLACK){
                afterRemove(treeNode,index,table);
            }
            if(treeNode.parent==null){
                table[index]=null;
            }
            else if(treeNode==treeNode.parent.left){
                treeNode.parent.left=null;
            }
            else if(treeNode==treeNode.parent.right){
                treeNode.parent.right=null;
            }
        }
        return null;
    }

    private void tryChangeToRedBlackTree(int hash) {
        if(size<MIN_TREEIFY_CAPACITY ){
            resize();
        }
        else {
            //链表转红黑树
            int index=index(hash,table.length);
            Node<K,V> current= (Node<K, V>) table[index];
            table[index]=null;
            TreeNode<K,V> head=null;
            TreeNode tail=null;
            while(current!=null){
                TreeNode<K, V> treeNode = toTreeNode(current);
                if(tail==null) {
                    head=tail=treeNode;
                }
                else{
                    tail.next=treeNode;
                    treeNode.prev=tail;
                    tail=treeNode;
                }
                current=current.next;
            }
            if(head!=null){
                System.out.println("hello world");
                table[index]=add(head);
            }
        }
    }
    private TreeNode<K,V> toTreeNode(Node<K,V> node){
        TreeNode<K,V> treeNode=new TreeNode<>(node.hash,node.key,node.value);
        return treeNode;
    }
    //扩容
    private void resize(){
        Entry<K,V> newTable[]=new Entry[table.length<<2];
        int oldCap=table.length;
        for(int i=0;i<oldCap;i++){
            if(table[i]!=null){
                Entry<K,V> entry=table[i];
                if(entry instanceof Node){
                    Node<K,V> node= (Node<K, V>) entry;
                    if(node.next==null){
                        newTable[node.hash&(oldCap-1)]=node;
                    }
                    else{
                        Node<K,V> lowHead=null;
                        Node<K,V> lowTail=null;
                        Node<K,V> highHead=null;
                        Node<K,V> highTail=null;
                        Node<K,V> next=null;
                        while(node!=null){
                            next=node.next;
                            if((node.hash&capacity)==0){
                                if(lowTail==null){
                                    lowHead=lowTail=node;
                                }
                                else{
                                    lowTail.next=node;
                                    lowTail=node;
                                }
                            }
                            else{
                                if(highTail==null){
                                    highHead=highTail=node;
                                }
                                else{
                                    highTail.next=node;
                                    highTail=node;
                                }
                            }
                            node=next;
                        }
                        if(lowHead!=null){
                            newTable[i]=lowHead;
                        }
                        if(highHead!=null){
                            newTable[i+oldCap]=highHead;
                        }
                    }
                }else{
                    //copy treeNode
                    TreeNode<K,V> treeNode= (TreeNode<K, V>) entry;
                    split(treeNode,i,oldCap,newTable);
                }
            }
        }
        this.table=newTable;
        this.capacity=newTable.length;
        this.threshold=(int)(loadFactor*this.capacity);
    }

    private int hash(K key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    private int index(int hash,int tableLength){
        return hash&(tableLength-1);
    }


    static class Node<K,V> implements Entry<K,V>{
        int hash;
        K key;
        V value;
        Node<K,V> next;
        public Node(int hash,K key,V value,Node<K,V> next){
            this.key=key;
            this.value=value;
            this.hash=hash;
            this.next=next;
        }
        public Node(int hash,K key,V value){
            this(hash,key,value,null);
        }
        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public void setKey(K key) {
            this.key=key;
        }

        @Override
        public void setValue(V value) {
            this.value=value;
        }
    }
    static class TreeNode<K,V> implements Entry<K,V>{
        int hash;
        K key;
        V value;
        boolean color;
        TreeNode<K,V> parent;
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;
        TreeNode<K,V> next;
        public TreeNode(int hash,K key,
                        V value,
                        TreeNode<K,V> parent,
                        TreeNode<K,V> left,
                        TreeNode<K,V> right,
                        TreeNode<K,V> prev,
                        TreeNode<K,V> next,
                        boolean color){
            this.hash=hash;
            this.key=key;
            this.value=value;
            this.parent=parent;
            this.left=left;
            this.right=right;
            this.prev=prev;
            this.next=next;
            this.color=color;
        }
        public TreeNode(int hash,K key,V value){
            this(hash,key,value,null,null,null,null,null,true);
        }
        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public void setKey(K key) {
            this.key=key;
        }

        @Override
        public void setValue(V value) {
            this.value=value;
        }
    }
    //以node为头节点将整条连边添加到红黑树中 并且返回整棵树的根节点
    public TreeNode<K,V> add(TreeNode<K,V> head){
        TreeNode<K,V> root=null;
        TreeNode<K,V> node=head;
        while(node!=null){
            if(root==null){
                root=node;
            }
            else{
                TreeNode<K,V> p=root;
                TreeNode<K,V> parent=null;
                boolean search=false;//标记是否已经查找过
                TreeNode<K,V> searchResult=null;
                int compare=0;
                while(p!=null){
                    parent=p;
                    int h1=node.hash;
                    int h2=p.hash;
                    if(h1>h2){
                        compare=1;
                    }
                    else if(h1<h2){
                        compare=-1;
                    }
                    else if(node.key!=null&&p.key!=null&&
                            node.key.getClass()==p.key.getClass()&&
                            node.key instanceof Comparable){
                        compare = ((Comparable) node.key).compareTo(p.key);
                    }

                    /**
                     * 如果已经搜索过了之后，不用在搜索，直接计算内存地址值
                     */
                    else if(search){
                        compare=System.identityHashCode(node.key)-System.identityHashCode(p.key);
                    }
                    else{
                        //向左边和右边查找是否存在相同的key，如果存在不用添加
                        if((p.left!=null&&(searchResult=node(p.left,node.key))!=null)||(p.right!=null&&(searchResult=node(p.right,node.key))!=null)){
                            compare=0;
                            p=searchResult;
                        }
                        //能来到这儿 说明不可比较 并且整颗二叉树中都不存在相同的key
                        else{
                            search=true;
                            compare=System.identityHashCode(node.key)-System.identityHashCode(p.key);
                        }
                    }
                    /**
                     * 一定要走到空才能添加，所以搜索应该缓存起来
                     */
                    if(compare>0){
                        p=p.right;
                    }
                    else if(compare<0){
                        p=p.left;
                    }
                    else{
                        V oldValue=p.value;
                        p.key=node.key;
                        p.value=node.value;
                    }
                }
                node.parent=parent;
                if(node.parent==null){
                    System.out.println("node.parent");
                }
                if(compare>0){
                    parent.right=node;
                }
                else if(compare<0){
                    parent.left=node;
                }
                root=afterAdd(root,node);
            }
            node=node.next;
        }
        return root;
    }
    public TreeNode<K,V> putTreeNode(TreeNode<K,V> root,TreeNode<K,V> node){
        TreeNode<K,V> parent=null;
        boolean search=false;//标记是否已经查找过
        TreeNode<K,V> searchResult=null;
        TreeNode<K,V> p=root;
        int compare=0;
        while(p!=null){
            parent=p;
            int h1=node.hash;
            int h2=p.hash;
            if(h1>h2){
                compare=1;
            }
            else if(h1<h2){
                compare=-1;
            }
            else if(node.key!=null&&p.key!=null&&
                    node.key.getClass()==p.key.getClass()&&
                    node.key instanceof Comparable){
                compare = ((Comparable) node.key).compareTo(p.key);
            }

            /**
             * 如果已经搜索过了之后，不用在搜索，直接计算内存地址值
             */
            else if(search){
                compare=System.identityHashCode(node.key)-System.identityHashCode(p.key);
            }
            else{
                //向左边和右边查找是否存在相同的key，如果存在不用添加
                if((p.left!=null&&(searchResult=node(p.left,node.key))!=null)||(p.right!=null&&(searchResult=node(p.right,node.key))!=null)){
                    compare=0;
                    p=searchResult;
                }
                //能来到这儿 说明不可比较 并且整颗二叉树中都不存在相同的key
                else{
                    search=true;
                    compare=System.identityHashCode(node.key)-System.identityHashCode(p.key);
                }
            }
            /**
             * 一定要走到空才能添加，所以搜索应该缓存起来
             */
            if(compare>0){
                p=p.right;
            }
            else if(compare<0){
                p=p.left;
            }
            else{
                V oldValue=p.value;
                p.key=node.key;
                p.value=node.value;
            }
        }
        node.parent=parent;
        if(node.parent==null){
            System.out.println("node.parent");
        }
        if(compare>0){
            parent.right=node;
        }
        else if(compare<0){
            parent.left=node;
        }
        root=afterAdd(root,node);
        return root;
    }
    private static final boolean RED=false;
    private static final boolean BLACK = true;
    private boolean colorOf(TreeNode<K,V> node){
        return node!=null?node.color:BLACK;
    }
    private void setColor(TreeNode<K,V> node,boolean color){
        if(node!=null){
            node.color=color;
        }
    }
    private TreeNode<K,V> leftOf(TreeNode<K,V> treeNode){
        return treeNode!=null?treeNode.left:null;
    }

    private TreeNode<K,V> rightOf(TreeNode<K,V> treeNode){
        return treeNode!=null?treeNode.right:null;
    }

    private TreeNode<K,V> parentOf(TreeNode<K,V> treeNode){
        return treeNode!=null?treeNode.parent:null;
    }
    private TreeNode<K,V> leftRotate(TreeNode<K,V> treeNode,TreeNode<K,V> root){
        if(treeNode!=null){
            TreeNode<K,V> rightNode=treeNode.right;
            treeNode.right=rightNode.left;
            if(rightNode.left!=null){
                rightNode.left.parent=treeNode;
            }
            rightNode.parent=treeNode.parent;
            if(treeNode.parent==null){
                root=rightNode;
            }
            else if(treeNode==treeNode.parent.left){
                treeNode.parent.left=rightNode;
            }
            else if(treeNode==treeNode.parent.right){
                treeNode.parent.right=rightNode;
            }
            treeNode.parent=rightNode;
            rightNode.left =treeNode;
        }
        return root;
    }
    private TreeNode<K,V> rightRotate(TreeNode<K,V> treeNode,TreeNode<K,V> root){
        if(treeNode!=null){
            TreeNode<K,V> leftNode=treeNode.left;
            treeNode.left=leftNode.right;
            if(leftNode.right!=null){
                leftNode.right.parent=treeNode;
            }
            leftNode.parent=treeNode.parent;
            if(treeNode.parent==null){
                root=leftNode;
            }
            else if(treeNode==treeNode.parent.left){
                treeNode.parent.left=leftNode;
            }
            else if(treeNode==treeNode.parent.right){
                treeNode.parent.right=leftNode;
            }
            treeNode.parent=leftNode;
            leftNode.right=treeNode;
        }
        return root;
    }
    private TreeNode<K,V> successor(TreeNode<K,V> treeNode){
        if(treeNode==null) return null;
        TreeNode<K,V> right=treeNode.right;
        if(right!=null){
            TreeNode<K,V> p=right;
            while(p.left !=null){
                p=p.left;
            }
            return p;
        }
        else{
            TreeNode<K,V> p=treeNode;
            TreeNode<K,V> parent=p.parent;
            while(parent!=null&&p==parent.right){
                p=parent;
                parent=parent.parent;
            }
            return parent;
        }
    }
    private TreeNode<K,V> predecessor(TreeNode<K,V> treeNode){
        if(treeNode==null) return null;
        TreeNode<K,V> left=treeNode.left;
        if(left!=null){
            TreeNode<K,V> p=left;
            while(p.right!=null){
                p=p.right;
            }
            return p;
        }
        else{
            TreeNode<K,V> p=treeNode;
            TreeNode<K,V> parent=p.parent;
            while(parent!=null&&p==parent.left){
                p=parent;
                parent=parent.parent;
            }
            return parent;
        }
    }
    private TreeNode<K,V> node(TreeNode<K,V> node,K key){
        if(node==null) return null;
        TreeNode<K, V> result = null;
        int compare=0;
        TreeNode<K,V> current=node;
        int h1=hash(key);
        int h2=0;
        while(current!=null){
            h2=current.hash;
            if(h1>h2){
                current=current.right;
            }
            else if(h1<h2){
                current=current.left;
            }
            else if(Objects.equals(key,current.key)){
                return current;
            }

            else if(key!=null&&current.key!=null&&key.getClass()==node.key.getClass()&&key instanceof Comparable&&(compare=((Comparable)key).compareTo(node.key))!=0){
                current=compare>0?current.right:current.left;
            }
            //向右递归搜索
            else if(current.right!=null&&(result=node(current.left,key))!=null){
                return result;
            }
            else{
                current=current.left;
            }
        }
        return null;
    }

    private TreeNode<K,V>  afterAdd(TreeNode<K,V> root,TreeNode<K,V> node) {
        if (node != null) {
            node.color = RED;
            if (node.parent == null) {
                System.out.println("java");
            }
            while (node != root && node.parent.color == RED) {
                if (parentOf(node) == leftOf(parentOf(parentOf(node)))) {
                    TreeNode<K, V> uncle = rightOf(parentOf(parentOf(node)));
                    //如果叔父节点不为空并且是红色 对应234树分裂情况
                    if (colorOf(uncle) == RED) {
                        setColor(parentOf(node), BLACK);
                        setColor(uncle, BLACK);
                        setColor(parentOf(parentOf(node)), BLACK);
                        node = parentOf(parentOf(node));
                    } else {
                        if (node == rightOf(parentOf(node))) {
                            root = leftRotate(parentOf(node), root);
                        }
                        setColor(parentOf(node), BLACK);
                        setColor(node, RED);
                        setColor(parentOf(parentOf(node)), RED);
                        root = rightRotate(parentOf(parentOf(node)), root);
                    }
                } else {
                    TreeNode<K, V> uncle = leftOf(parentOf(parentOf(node)));
                    //如果叔父节点不为空并且是红色 对应234树分裂情况
                    if (colorOf(uncle) == RED) {
                        setColor(parentOf(node), BLACK);
                        setColor(uncle, BLACK);
                        setColor(parentOf(parentOf(node)), BLACK);
                        node = parentOf(parentOf(node));
                    } else {
                        if (node == leftOf(parentOf(node))) {
                            root = rightRotate(parentOf(node), root);
                        }
                        setColor(parentOf(node), BLACK);
                        setColor(node, RED);
                        setColor(parentOf(parentOf(node)), RED);
                        root = leftRotate(parentOf(parentOf(node)), root);
                    }
                }
            }
        }
        return root;
    }
    private void afterRemove(TreeNode<K,V> x,int index,Entry<K,V>[] table){
        while(table[index] != x &&colorOf(x)==BLACK){
            if(x==leftOf(parentOf(x))){
                //寻找兄弟节点
                TreeNode<K,V> slider=rightOf(parentOf(x));
                if(colorOf(slider)==RED){
                    //将兄弟节点黑
                    //将父节点变红
                    setColor(parentOf(x),RED);
                    setColor(slider,BLACK);
                    table[index]=leftRotate(parentOf(x),(TreeNode<K, V>) table[index]);
                    //重新找到真正的兄弟节点
                    slider=rightOf(parentOf(x));
                }


                //熊第节点的做和右都为空
                if(colorOf(leftOf(slider))==BLACK&&colorOf(rightOf(slider))==BLACK){
                    setColor(slider,RED);
                    x=parentOf(x);
                }

                //左右节点有红色节点和空节点 红色节点和黑色节点
                else{
                    //如果兄弟节点的右节点为空或者是黑色节点
                    if(colorOf(rightOf(slider))==BLACK){
                        setColor(slider,RED);
                        setColor(leftOf(slider),BLACK);
                        table[index]=rightRotate(slider,(TreeNode<K,V>)table[index]);
                        slider=rightOf(parentOf(x));
                    }
                    setColor(rightOf(slider),BLACK);
                    setColor(slider,colorOf(parentOf(x)));
                    setColor(parentOf(x),BLACK);
                    table[index]=leftRotate(parentOf(x),(TreeNode<K,V>)table[index]);
                    x= (TreeNode<K, V>) table[index];
                }
            }
            else{
                //寻找兄弟节点
                TreeNode<K,V> slider=leftOf(parentOf(x));
                if(colorOf(slider)==RED){
                    //将兄弟节点黑
                    //将父节点变红
                    setColor(parentOf(x),RED);
                    setColor(slider,BLACK);
                    table[index]=rightRotate(parentOf(x),(TreeNode<K, V>) table[index]);
                    //重新找到真正的兄弟节点
                    slider=leftOf(parentOf(x));
                }
                //熊第节点的做和右都为空
                if(colorOf(leftOf(slider))==BLACK&&colorOf(rightOf(slider))==BLACK){
                    setColor(slider,RED);
                    x=parentOf(x);
                }

                //左右节点有红色节点和空节点 红色节点和黑色节点
                else{
                    //如果兄弟节点的右节点为空或者是黑色节点
                    if(colorOf(leftOf(slider))==BLACK){
                        setColor(slider,RED);
                        setColor(rightOf(slider),BLACK);
                        table[index]=leftRotate(slider,(TreeNode<K,V>)table[index]);
                        slider=leftOf(parentOf(x));
                    }
                    setColor(leftOf(slider),BLACK);
                    setColor(slider,colorOf(parentOf(x)));
                    setColor(parentOf(x),BLACK);
                    table[index]=rightRotate(parentOf(x),(TreeNode<K,V>)table[index]);
                    x= (TreeNode<K, V>) table[index];
                }
            }
        }
        setColor(x,BLACK);
    }
    private void split(TreeNode<K,V> root,int index,int bit,Entry<K,V> []newTable){
        TreeNode<K,V> node=root;
        TreeNode<K,V> loHead=null,loTail=null;
        TreeNode<K,V> highHead=null,highTail=null;
        TreeNode<K,V> next=null;
        int lc=0;
        int hc=0;
        while(node!=null){
            next=node.next;
            if((node.hash&bit)==0){
                lc++;
                if(loTail==null) {
                    loTail=loHead=node;
                }
                else{
                    loTail.next=node;
                    node.prev=loTail;
                    loTail=node;
                }
            }
            else{
                hc++;
                if(highTail==null) {
                    highHead=highTail=node;
                }
                else{
                    highTail.next=node;
                    node.prev=highTail;
                    highTail=node;
                }
            }
            node=next;
        }
        if(loHead!=null){
            if(lc<=UNTREEIFY_THRESHOLD){
                newTable[index]=toNode(loHead);
            }
            else{
                TreeNode<K, V> h = add(loHead);
                newTable[index+bit]=h;
            }
        }
        if(highHead!=null){
            if(hc<=UNTREEIFY_THRESHOLD){
                newTable[index+bit]=toNode(highHead);
            }else{
                TreeNode<K, V> h = add(highHead);
                newTable[index+bit]=h;
            }
        }
    }
    private void show(int index){
        if(table[index]!=null){
            Entry<K,V> entry=table[index];
            if(entry instanceof Node){
                Node<K,V> node=(Node)entry;
                while(node!=null){
                    System.out.println(node.key+"========"+node.value);
                    node=node.next;
                }
            }
            else{
                TreeNode<K,V> treeNode=(TreeNode<K,V>)entry;

            }
        }
    }
    private void preOrder(TreeNode<K,V> treeNode){
        if(treeNode==null) return ;
        System.out.println(treeNode.key+"========"+treeNode.value);
        preOrder(treeNode.left);
        preOrder(treeNode.right);
    }
    private void inOrder(TreeNode<K,V> treeNode){
        if(treeNode==null) return ;
        inOrder(treeNode.left);
        System.out.println(treeNode.key+"========"+treeNode.value);
        inOrder(treeNode.right);
    }
    private void postOrder(TreeNode<K,V> treeNode){
        if(treeNode==null) return ;
        postOrder(treeNode.left);
        System.out.println(treeNode.key+"========"+treeNode.value);
        postOrder(treeNode.right);
    }
    private Node<K,V> toNode(TreeNode<K,V> treeNode){
        TreeNode<K,V> node=treeNode;
        Node<K,V> head=null;
        Node<K,V> tail=null;
        TreeNode<K,V> next=null;
        while(node!=null){
            next=node.next;
            Node<K,V> newNode= new Node<>(node.hash,node.key,node.value,null);
            if(tail==null){
                head=tail=newNode;
            }else{
                tail.next=newNode;
                tail=newNode;
            }
            node=next;
        }
        return head;
    }

    private int height(TreeNode<K,V> treeNode){
        if(treeNode==null) return 0;
        else if(treeNode.left==null&&treeNode.right==null){
            return 1;
        }
        return 1+Math.max(height(treeNode.left),height(treeNode.right));
    }
    public Map<Integer,Integer> countNode(){
        Map<Integer,Integer> map = new java.util.HashMap<>();
        for(int index=0;index<table.length;index++){
            int v=countIndexNode(index);
            map.put(index,v);
        }
        return map;
    }
    public int countIndexNode(int index){
        if(table[index]==null) return 0;
        Entry<K,V> entry=table[index];
        int count=0;
        if(entry instanceof Node){
            Node<K,V> node=(Node<K,V>)entry;

            while(node!=null){
                count++;
                node=node.next;
            }
            return count;
        }
        else{
            TreeNode<K,V> treeNode=(TreeNode<K,V>)entry;
            count=countTreeNode(treeNode);
        }
        return count;
    }
    private int countTreeNode(TreeNode<K,V> treeNode){
        if(treeNode==null) return 0;
        if(treeNode.left==null&&treeNode.right==null) return 1;
        return 1+countTreeNode(treeNode.left)+countTreeNode(treeNode.right);
    }
    private boolean isValidRedBlackTree(TreeNode<K,V> root){
        if(root==null||root.color!=BLACK){
            return false;
        }
        List<Integer> list=new ArrayList<>();
        boolean [] valid=new boolean[]{true};
        dfsValidRedBlackTree(valid,root,0,list);
        return valid[0];
    }
    private void dfsValidRedBlackTree(boolean [] valid,TreeNode<K,V> node, int sum, List<Integer> list){
        if(node==null){
            list.add(sum+1);
            return ;
        }
        //统计每条路径黑色节点的个数
        if(node.color==BLACK){
            sum++;
        }
        if(node.color==RED){
            if(node.left!=null){
                if(node.left.color==RED){
                    valid[0]=false;
                }
            }
            if(node.right!=null){
                if(node.right.color==RED){
                    valid[0]=false;
                }
            }
        }
        dfsValidRedBlackTree(valid,node.left,sum,list);
        dfsValidRedBlackTree(valid,node.right,sum,list);
    }
}
